package cn.dlc.com.tree;

import cn.dlc.com.queue.Queue;
import lombok.AllArgsConstructor;
import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/23 22:06
 * @desc 折纸类
 */
public class ZhezhiDemo {

    @Data
    @AllArgsConstructor
    private static class Node<T> {
        private T item;
        private Node<T> left;
        private Node<T> right;
    }

    /**
     * 创建这一个折纸树，通过层序遍历的思想
      * @param num 折纸的次数
     * @return 返回折纸树的根节点
     */
    public static Node<String> createTree(int num){

        Node<String> root = null;

        for (int i = 0; i < num; i++) {
            // 如果是第一次
            if(i == 0) {
                // 第一个节点的折痕是down
                root = new Node<>("down",null, null);
                // 继续循环
                continue;
            }

            // 定义一个辅助队列
            Queue<Node<String>> queue = new Queue<>();
            queue.enQueue(root);

            while (!queue.isEmpty()) {

                // 出来一个
                Node<String> node = queue.deQueue();

                // 有左子节点，吧左子节点方进去
                if(node.getLeft() != null) {
                    queue.enQueue(node.getLeft());
                }

                // 如果有右子结点，把右子结点方进去
                if(node.getRight() != null) {
                    queue.enQueue(node.getRight());
                }

                // 如果都没有
                if(node.getRight() == null && node.getLeft() == null) {
                    node.setRight(new Node<>("down", null, null));
                    node.setLeft(new Node<>("up", null, null));
                }
            }
        }

        return root;
    }

    // 中序遍历
    private static void printTree(Node<String> root){
        if(root == null) {
            return;
        }

        if(root.getLeft() != null) {
            printTree(root.getLeft());
        }

        // 直接打印
        System.out.print(root.getItem() + " ");

        if(root.getRight() != null) {
            printTree(root.getRight());
        }
    }

    public static void main(String[] args) {
        Node<String> tree = createTree(3);
        printTree(tree);
    }
}
